/*
https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/
 */
import java.util.HashSet;
import java.util.Set;

public class Solution959 {
    public int regionsBySlashes(String[] grid) {
        int n=grid.length;
        int[] b=new int[n*n*4];
        for (int i=0;i<b.length;i++){
            b[i]=i;
        }
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++){
                if (grid[i].charAt(j)==' '){
                    union(b,(i*n+j)*4,(i*n+j)*4+1);
                    union(b,(i*n+j)*4,(i*n+j)*4+2);
                    union(b,(i*n+j)*4,(i*n+j)*4+3);
                }else if (grid[i].charAt(j)=='/'){
                    union(b,(i*n+j)*4,(i*n+j)*4+1);
                    union(b,(i*n+j)*4+2,(i*n+j)*4+3);
                }else{
                    union(b,(i*n+j)*4,(i*n+j)*4+2);
                    union(b,(i*n+j)*4+1,(i*n+j)*4+3);
                }
            }
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (i!=n-1){
                    union(b,(i*n+j)*4+3,((i+1)*n+j)*4);
                }
                if (j!=n-1){
                    union(b,(i*n+j)*4+2,(i*n+j+1)*4+1);
                }
            }
        }
        Set<Integer> set=new HashSet<>();
        for (int i=0;i<n*n*4;i++){
            set.add(find(b,i));
        }
        return set.size();
    }

    private int find(int[] b, int i) {
        while (i!=b[i]){
            i=b[i];
        }
        return i;
    }

    public void union(int[] b,int i,int j){
        int x=find(b,i);
        int y=find(b,j);
        b[x]=y;
    }

    public static void main(String[] args) {
        System.out.println(new Solution959().regionsBySlashes(new String[]{" /","/ "}));
    }
}
